//
// Created by DengLibin on 2018/12/16 0016.
//

#include <iostream>
#include <string>
using namespace std;

//静态队列（数组实现）
/*
	1、队列:一端进，另一端出；队列由两个参数决定，front(头),rear(尾)；
	头指针指向头一个元素，尾指针指向指向最后一个元素的下一存储单元；若数组长度为n，当元素个数为n-1时就认为队列已满。r指向最后一个空的元素空间。

	出队：头指针往上移动，

	入队：尾指针向上移动，故：静态队列只能是循环队列，不然出队的元素占用的空间
	永远无法重复利用。

	1）：队列的初始化:front,rear的值都是零、
	2）：队列非空：front代表的是队列的第一个元素,rear代表的是队列的最后一个元素的下个存储单元
	3) ：队列空:front和rear的值相等，但不一定是零
	4）：动态队列：链表实现
	     静态队列：数组实现

2、循环队列:
	出队:f = (f+1) % 数组长度
	入队：r = (r+1) % 数组长度

		+++++++++++++++++++++
		+		    +
		+	3	    +<----r
		+		    +
		+++++++++++++++++++++
		+		    +
		+	2	    +
		+		    +
		+++++++++++++++++++++
		+		    +
		+	1	    +
		+		    +
		+++++++++++++++++++++
		+		    +
 f ---> +	0	    +
		+		    +
		+++++++++++++++++++++

	如何判断循环队列是否为空: 如果f == r 就一定为空
	如何判断队列已满：
		1）增加一个标志n记录队列元素的个数，当n = 数组长度-1时，就满了。
		2)if((r+1)%arr.length == f){
			队列已满
		}
		通常使用第二种

*/
template<class T>
class Queue
{
private:
    int len = 8;//长度
    T* data; //数据
    int headIndex = 0;//头指针(初始值为0，指向第一个元素)
    int tailIndex = 0;//尾指针
public:
    //无参构造函数
    Queue()
    {
        this(len);
    }
    //构造函数
    Queue(int len)
    {
        this->len = len;
        this->data = new T[len + 1]{nullptr}; //创建数组对象
    }
    //析构函数
    ~Queue()
    {
        //释放内存空间
        for (int i = 0; i < len; i++)
        {
            if (data[i] != nullptr)
            {
                delete data[i];
            }
        }
        delete[] data;
        cout << "析构队列" << endl;
    }
    //是否为空
    bool isEmpty()
    {
        return headIndex == tailIndex;
    }
    //是否已满
    bool isFull()
    {
        return (tailIndex + 1) % (len + 1) == headIndex;
    }
    //入队
    void put(T t)
    {
        if (isFull())
        {
            cout << "队列已满" << endl;
            return;
        }
        data[tailIndex] = t;
        tailIndex = (tailIndex + 1) % (len + 1);
    }
    //出队
    T take()
    {
        if (isEmpty())
        {
            cout << "队列已空" << endl;
            return nullptr;
        }
        T t =  data[headIndex];
        data[headIndex] = nullptr;
        headIndex = (headIndex + 1) % (len + 1);
        return t;
    }
};

//类
class Cat
{
private:
    int age;
    string name;
public:
    Cat(int age, string& name)
    {
        this->age = age;
        this->name = name;
    }
    ~Cat()
    {
        cout <<"析构Cat" << endl;
    }
    int getAge()
    {
        return age;
    }
    string & getName()
    {
        return this->name;
    }
};
//测试队列
void testQueue()
{
    int len = 5;
    Queue<Cat*> * queue = new Queue<Cat*>(len);
    //入队
    for (int i = 0; i <len; i++)
    {
        string name = "小花";
        queue->put(new Cat(i, name));
    }
    //出队
    for (int i = 0; i < 6; i++)
    {
        Cat * cat = queue->take();
        if (cat == nullptr)
        {
            continue;
        }
        cout << cat->getAge() << "," << cat->getName() << endl;
        delete cat;
    }

    delete queue;
}

int main44()
{
    testQueue();
    getchar();
    return 0;
}